《剑指offer》 24. 反转链表

note: 反转链表作为一道简单题,主要考察的是对迭代法和链表数据结构的了解。

题目描述

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

限制:

1
0 <= 节点个数 <= 5000

方法一 迭代法

思路

首先我们需要一个指向前一个节点的指针pre,然后每次迭代做四件事

  1. 保存当前节点的下个节点
  2. 让当前节点的下一个节点指针改为指向pre指针指向的节点
  3. 让pre指针指向当前节点
  4. 让指向当前节点的指针指向下个节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode * pre = NULL;
while(head!=NULL){
ListNode* temp = head->next;
head->next = pre;
pre=head;
head = temp;
}
return pre;
}
};

复杂度分析

  • 时间复杂度$O(n)$。需要遍历每个节点
  • 空间复杂度$O(1)$。只需要一个pre指针,常量级空间。

方法二 递归法

思路

递归的思路其实就是分治,将每部分都要反转的问题,转化为思考现在我有一个节点和它后续已经反转好的节点。思考到这一步就差不多能写出来了。递归终止条件为当前节点的下个节点为空(说明已经是最后一个节点)或者当前节点为空(说明链表为空),此时返回当前节点。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL || head->next==NULL)
return head;
ListNode* cur = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return cur;
}
};

复杂度分析

  • 时间复杂度$O(n)$。需要遍历每个节点
  • 空间复杂度$O(n)$。递归需要调用栈空间,显然需要链表长度层栈空间。